5.3 Operaciones básicas con listas doblemente enlazadas:  

De nuevo tenemos el mismo repertorio de operaciones sobre este tipo listas:

• Añadir o insertar elementos.
• Buscar o localizar elementos.
• Borrar elementos.
• Moverse a través de la lista, siguiente y anterior.

5.4 Añadir un elemento:  

Nos encontramos ahora ante un tipo de estructura algo diferente de las que hemos estado viendo, así que entraremos en más detalles.

Vamos a intentar ver todos los casos posibles de inserción de elementos en listas doblemente enlazadas.

Añadir elemento en una lista doblemente enlazada vacía:

Partiremos de que ya tenemos el nodo a insertar y, por supuesto un puntero que apunte a él, además el puntero que define la lista, que valdrá NULL:

El proceso es muy simple, bastará con que:

1. lista apunta a nodo.
2. lista->siguiente y lista->anterior apunten a null.

Insertar un elemento en la primera posición de la lista:

Partimos de una lista no vacía. Para simplificar, consideraremos que lista apunta al primer elemento de la lista doblemente enlazada:

El proceso es el siguiente:

1. nodo->siguiente debe apuntar a Lista.
2. nodo->anterior apuntará a Lista->anterior.
3. Lista->anterior debe apuntar a nodo.

Recuerda que Lista no tiene por qué apuntar a ningún miembro concreto de una lista doblemente enlazada, cualquier miembro es igualmente válido como referencia.

Insertar un elemento en la última posición de la lista:

Igual que en el caso anterior, partiremos de una lista no vacía, y de nuevo para simplificar, que Lista está apuntando al último elemento de la lista:

El proceso es el siguiente:

1. nodo->siguiente debe apuntar a Lista->siguiente (NULL).
2. Lista->siguiente debe apuntar a nodo.
3. nodo->anterior apuntará a Lista.

Insertar un elemento a continuación de un nodo cualquiera de una lista:

Bien, este caso es más genérico, ahora partimos de una lista no vacía, e insertaremos un nodo a continuación de uno nodo cualquiera que no sea el último de la lista:

El proceso sigue siendo muy sencillo:

1. Hacemos que nodo->siguiente apunte a lista->siguiente.
2. Hacemos que Lista->siguiente apunte a nodo.
3. Hacemos que nodo->anterior apunte a lista.
4. Hacemos que nodo->siguiente->anterior apunte a nodo.

Lo que hemos hecho es trabajar como si tuviéramos dos listas enlazadas, los dos primeros pasos equivalen a lo que hacíamos para insertar elementos en una lista abierta corriente.

Los dos siguientes pasos hacen lo mismo con la lista que enlaza los nodos en sentido contrario.

El paso 4 es el más oscuro, quizás requiera alguna explicación.

Supongamos que disponemos de un puntero auxiliar, "p" y que antes de empezar a insertar nodo, hacemos que apunte al nodo que quedará a continuación de nodo después de insertarlo, es decir p = Lista->siguiente.

Ahora empezamos el proceso de inserción, ejecutamos los pasos 1, 2 y 3. El cuarto sería sólo hacer que p->anterior apunte a nodo. Pero nodo->siguiente ya apunta a p, así que en realidad no necesitamos el puntero auxiliar, bastará con hacer que nodo->siguiente->anterior apunte a nodo.

Añadir elemento en una lista doblemente enlazada, caso general:

Para generalizar todos los casos anteriores, sólo necesitamos añadir una operación:

1. Si lista está vacía hacemos que Lista apunte a nodo. Y nodo->anterior y nodo->siguiente a NULL.
2. Si lista no está vacía, hacemos que nodo->siguiente apunte a Lista->siguiente.
3. Después que Lista->siguiente apunte a nodo.
4. Hacemos que nodo->anterior apunte a Lista.
5. Si nodo->siguiente no es NULL, entonces hacemos que nodo->siguiente->anterior apunte a nodo.

El paso 1 es equivalente a insertar un nodo en una lista vacía.

Los pasos 2 y 3 equivalen a la inserción en una lista enlazada corriente.

Los pasos 4, 5 equivalen a insertar en una lista que recorre los nodos en sentido contrario.

Existen más casos, las listas doblemente enlazadas son mucho más versátiles, pero todos los casos pueden reducirse a uno de los que hemos explicado aquí.